/*
*	回溯和剪枝
*/


//全排列
//https://leetcode.cn/problems/permutations/description/
// class Solution {
//     vector<vector<int>> ret;
//     vector<int> path;
//     int check[7];
// public:
//     vector<vector<int>> permute(vector<int>& nums) {
//         dfs(nums);
//         return ret;
//     }

//     void dfs(vector<int>& nums)
//     {
//         if(nums.size() == path.size())
//         {
//             ret.push_back(path);
//             return;
//         }

//         for(int i = 0;i<nums.size();++i)
//         {
//             //如果这个数没有被选过则进入
//             if(!check[i])
//             {
//                 path.push_back(nums[i]);
//                 check[i] = true;
//                 dfs(nums);
//                 path.pop_back();
//                 check[i] = false;
//             }
//         }
//     }
// };


//子集
//https://leetcode.cn/problems/subsets/description/
// class Solution {
//     vector<vector<int>> ret;
//     vector<int> path;
// public:
//     vector<vector<int>> subsets(vector<int>& nums) {
//         dfs(nums,0);
//         return ret;
//     }

//     void dfs(vector<int>& nums,int pos)
//     {
//         //第一次调用表示0个元素
//         //第一次递归表示1个元素
//         //第二次递归表示选择两个元素
//         //...
//         //每一层开始就是一个结果
//         ret.push_back(path);
//         //pos表示下次从哪一个元素开始
//         for(int i = pos;i<nums.size();++i)
//         {
//             path.push_back(nums[i]);
//             dfs(nums,i+1); //从下一个元素开始
//             path.pop_back(); //回溯
//         }
//     }
// };


//找出所有子集的异或总和再求和
//https://leetcode.cn/problems/sum-of-all-subset-xor-totals/submissions/
// class Solution {
// public:
//     int path;
//     int ret = 0;
//     int subsetXORSum(vector<int>& nums) {
//         if(nums.size() == 0) return 0;
//         dfs(nums,0);
//         return ret;
//     }

//     void dfs(vector<int> nums,int pos)
//     {
//         ret += path;
//         for(int i = pos;i<nums.size();++i) {

//             path ^= nums[i];
//             dfs(nums,i+1);
//             path ^= nums[i];
//         }

//     }
// };


//47.全排列Ⅱ
//https://leetcode.cn/problems/permutations-ii/submissions/
// class Solution {
// public:
//     vector<vector<int>> ret;
//     vector<int> path;
//     bool check[9];
//     vector<vector<int>> permuteUnique(vector<int>& nums) {
//         sort(nums.begin(),nums.end());
//         dfs(nums);
//         return ret;
//     }

//     void dfs(vector<int>& nums)
//     {
//         if(path.size() == nums.size())
//         {
//             ret.push_back(path);
//             return;
//         }
//         for(int i = 0;i<nums.size();++i)
//         {
//             //如果当前位置没有选择 且
//             //当前位置是第一个数 或 当前位置与上一个数非相同 或 上一个数已经被上一层选择
//             //则满足条件
//             if(check[i] == false && (i == 0 || nums[i]!=nums[i-1] || check[i-1]))
//             {
//                 check[i] = true; //标记已经使用
//                 path.push_back(nums[i]);
//                 dfs(nums);
//                 path.pop_back();
//                 check[i] = false;
//             }

//         }
//     }
// };


//电话号码的字母组合
//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
// class Solution {
//     vector<string> ret;
//     string path;
//     const string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

// public:
//     vector<string> letterCombinations(string digits) {
//             if(digits.empty()) return ret;
//             dfs(digits, 0);
//             return ret;
//     }

//     //pos表示当前在第几个数字
//     void dfs(string& digits, int pos)
//     {
//         if (path.size() == digits.size())
//         {
//             ret.push_back(path);
//             return;
//         }

//         for (const auto& c : hash[digits[pos] - '0'])
//         {
//             path.push_back(c);
//             dfs(digits, pos + 1);
//             path.pop_back();
//         }
//     }
// };


//括号生成
//https://leetcode.cn/problems/generate-parentheses/submissions/
// class Solution {
//     vector<string> ret;
//     string path;
//     int left = 0,right = 0;
// public:
//     vector<string> generateParenthesis(int n) {
//         dfs(n);
//         return ret;
//     }

//     void dfs(int n)
//     {
//         if(path.size() == 2*n)
//         {
//             ret.push_back(path);
//             return;
//         }

//         if(left < n)
//         {
//             path.push_back('(');
//             ++left;
//             dfs(n);
//             --left;
//             path.pop_back();
//         }

//         if(right < n && right < left)
//         {
//             path.push_back(')');
//             ++right;
//             dfs(n);
//             --right;
//             path.pop_back();
//         }
//     }
// };


//组合
//https://leetcode.cn/problems/combinations/submissions/
// class Solution {
//     vector<vector<int>> ret;
//     vector<int> path;
// public:
//     vector<vector<int>> combine(int n, int k) {
//         dfs(1,n,k);
//         return ret;
//     }

//     void dfs(int begin,int end,int k)
//     {
//         if(path.size() == k)
//         {
//             ret.push_back(path);
//             return;
//         }

//         for(int i = begin;i<=end;++i)
//         {
//             path.push_back(i);
//             dfs(i+1,end,k);
//             path.pop_back();
//         }
//     }
// };


//目标和
//https://leetcode.cn/problems/target-sum/description/
// class Solution {
//     int ret = 0;
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         dfs(nums,target,0,0);
//         return ret;
//     }

//     void dfs(vector<int>& nums, int target,int pos,int path)
//     {
//         if(nums.size() == pos)
//         {
//             if(path == target) ++ret;
//             return;
//         }
        
//         dfs(nums,target,pos+1,path + nums[pos]);
        
//         dfs(nums,target,pos+1,path - nums[pos]);
        
//     }
// };


//组合总和
//https://leetcode.cn/problems/combination-sum/submissions/
// class Solution {
//     vector<vector<int>> ret;
//     vector<int> path;
// public:
//     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//         dfs(candidates,target,0,0);
//         return ret;
//     }

//     void dfs(vector<int>& candidates,int target,int sum,int pos)
//     {
//         if(sum >= target || pos == candidates.size())
//         {
//             if(sum == target) ret.push_back(path);
//             return;
//         }

//         //解法一
//         //每一层选一个数 可以选重复的 但是不能选pos之前的
//         // for(int i = pos;i<candidates.size();++i) 
//         // {
//         //     path.push_back(candidates[i]);
//         //     dfs(candidates,target,sum + candidates[i],i);
//         //     path.pop_back();
//         // }

//         //解法二
//         //枚举每一层可以取多少个pos下的数
//         for(int k = 0;k*candidates[pos] <= target;++k)
//         {
//             if(k) path.push_back(candidates[pos]);
//             dfs(candidates,target,sum+k*candidates[pos],pos+1);
//         }

//         //回溯
//         for(int k = 1;k*candidates[pos] <= target;++k) path.pop_back();
//     }
// };


//字母大小写全排列
//https://leetcode.cn/problems/letter-case-permutation/submissions/
// class Solution {
//     vector<string> ret;
//     string path;
// public:
//     vector<string> letterCasePermutation(string s) {
//         dfs(s,0);
//         return ret;
//     }

//     void dfs(string& s,int pos)
//     {
//         if(pos == s.size())
//         {
//             if(path.size() == s.size()) ret.push_back(path);
//             return;
//         }

//             char ch = s[pos];
//             //小写变大写
//             if('a'<=ch && ch <= 'z') 
//             {
//                 path.push_back(ch-32);
//                 dfs(s,pos+1);
//                 path.pop_back();
//             }
//             //大写变小写
//             else if('A'<=ch && ch <= 'Z') 
//             {
//                 path.push_back(ch+32);
//                 dfs(s,pos+1);
//                 path.pop_back();
//             }
            
//             //不改变 && 数字直接继续遍历
//             path.push_back(ch);
//             dfs(s,pos+1);
//             path.pop_back();
//     }
// };


//优美的排列
//https://leetcode.cn/problems/beautiful-arrangement/submissions/
// class Solution {
//     int ret = 0;
//     bool check[16];
// public:
//     int countArrangement(int n) {
//         dfs(n,1);
//         return ret;
//     }

//     void dfs(int n,int pos)
//     {
//         if(pos == n+1) 
//         {
//             ++ret;
//             return;
//         }

//         //每一层确定一个排列数 当到n+1时排列组成完成
//         for(int i = 1;i<=n;++i)
//         {
//             //当前位置的数没有被枚举 则判断是否可以与pos组成排列
//             if(!check[i] && (pos % i == 0 || i % pos == 0))
//             {
//                 check[i] = true;
//                 dfs(n,pos+1);
//                 check[i] = false;
//             }
//         }
        
//     }
// };


//N皇后
//https://leetcode.cn/problems/n-queens/submissions/
// class Solution {
//     vector<vector<string>> ret;
//     vector<string> path;
//     vector<bool> column,loblique,roblique;
//     //column标记一列，如果该列被放置皇后 则该整列都不符合要求
//     //关于loblique和roblique标记左斜和右斜上是否有皇后 我们只需要知道是否有而不需要知道具体位置 左右斜边有一个就算有
// public:
//     vector<vector<string>> solveNQueens(int n) {
//         column.resize(n,false);
//         loblique.resize(2*n,false);
//         roblique.resize(2*n,false);
//         path.resize(n,string(n,'.'));
//         dfs(n,0);
//         return ret;
//     }

//     //控制行
//     void dfs(const int maxrow,int row)
//     {
//         if(maxrow == row)
//         {
//             ret.push_back(path);
//             return;
//         }

//         //控制列
//         for(int col = 0;col<maxrow;++col)
//         {
//             if(!column[col] && !loblique[row+col] && !roblique[row-col+maxrow])
//             {
//                 column[col] = loblique[row+col] = roblique[row-col+maxrow] = true;
//                 path[row][col] = 'Q';
//                 dfs(maxrow,row+1);
//                 path[row][col] = '.';
//                 column[col] = loblique[row+col] = roblique[row-col+maxrow] = false;
//             }
//         }
//     }
// };


//有效的数独
//https://leetcode.cn/problems/valid-sudoku/description/
// class Solution {
//     bool row[9][10];
//     bool col[9][10];
//     bool grid[3][3][10];

// public:
//     bool isValidSudoku(vector<vector<char>>& board) {
//         for(int i = 0;i<9;++i)
//             for(int k = 0;k<9;++k)
//             {
//                 if(board[i][k] == '.') continue;
//                 int num = board[i][k] - '0';
//                 if(row[i][num] || col[k][num] || grid[i/3][k/3][num]) return false;
//                 row[i][num] = col[k][num] = grid[i/3][k/3][num] = true;
//             }

//         return true;
//     }
// };


//解数独
//https://leetcode.cn/problems/sudoku-solver/submissions/
// class Solution {
//     bool row[9][10];
//     bool col[9][10];
//     bool grid[3][3][10];
// public:
//     void solveSudoku(vector<vector<char>>& board) {
//         for(int i = 0;i<9;++i)
//             for(int k = 0;k<9;++k)
//             {
//                 if(board[i][k] == '.') continue;
//                 int num = board[i][k] - '0';
//                 row[i][num] = col[k][num] = grid[i/3][k/3][num] = true;
//             }

//         dfs(board);
//     }

//     //函数每一次找一个空位 尝试填入一个数字 然后递归填其他数字
//     //一旦在递归中发现无法填入 则表示前面填入的有误 则会回溯到最开始 换其他数字填入再递归
//     bool dfs(vector<vector<char>>& board)
//     {
//         for(int i = 0;i<9;++i)
//             for(int k = 0;k<9;++k)
//             {
//                 if(board[i][k] == '.')
//                 {
//                     for(int n = 1;n<10;++n)
//                     {
//                         if(row[i][n] || col[k][n] || grid[i/3][k/3][n]) continue;
//                         board[i][k] = n+'0';
//                         row[i][n] = col[k][n] = grid[i/3][k/3][n] = true;
//                         if(dfs(board)) return true; //递归全部填完则停止
//                         board[i][k] = '.';
//                         row[i][n] = col[k][n] = grid[i/3][k/3][n] = false;
//                     }
//                     return false;//如果一轮没有填入任何数字 则表示上面的填写有问题
//                 }
//             }

//         return true;
//     }
// };


//单词搜索
//https://leetcode.cn/problems/word-search/submissions/
// class Solution {
//     vector<vector<bool>> check;
//     //对应上下左右四个坐标
//     int dx[4] = {-1,1,0,0};
//     int dy[4] = {0,0,-1,1};
// public:
//     bool exist(vector<vector<char>>& board, string word) {
//         check.resize(board.size(),vector<bool>(board[0].size()));
//         int x = 0,y = 0;
//         for(int i = 0;i<board.size();++i)
//             for(int k = 0;k<board[0].size();++k)
//             {
//                 if(board[i][k] == word.front())
//                 {
//                     check[i][k] = true;
//                     //找到第一个与之匹配的字符 开始回溯
//                     if(dfs(board,word,i,k,1)) return true;
//                     check[i][k] = false;
//                 }
//             }
//         return false;
//     }

//     bool dfs(const vector<vector<char>>& board,const string& word,int x,int y,int pos) {
//         if(pos == word.size()) return true;
//         for(int i = 0;i<4;++i)
//         {
//             int posx = x+dx[i],posy = y+dy[i];
//             if(posx >= 0 && posx < board.size() && posy >= 0 && posy < board[0].size() && !check[posx][posy] && board[posx][posy] == word[pos])
//             {
//                 check[posx][posy] = true;
//                 if(dfs(board,word,posx,posy,pos+1)) return true;
//                 check[posx][posy] = false;
//             }
//         }
//         return false;
//     }
// };


//黄金矿工
//https://leetcode.cn/problems/path-with-maximum-gold/submissions/
// class Solution {
//     vector<vector<bool>> check;
//     int ret = 0;
//     int m = 0,n = 0;
//     int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};
// public:
//     int getMaximumGold(vector<vector<int>>& grid) {
//         m = grid.size(),n = grid[0].size();
//         check.resize(m,vector<bool>(n));
//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//             {
//                 if(grid[i][k])
//                 {
//                     check[i][k] = true;
//                     dfs(grid,i,k,grid[i][k]);
//                     check[i][k] = false;
//                 }
//             }

//         return ret;
//     }

//     void dfs(vector<vector<int>>& grid,int x,int y,int path)
//     {
//         ret = max(ret,path);
//         for(int i = 0;i<4;++i)
//         {
//             int posx = x+dx[i],posy = y+dy[i];
//             if(posx < m && posx >= 0 && posy < n && posy >=0 && !check[posx][posy] && grid[posx][posy])
//             {
//                 check[posx][posy] = true;
//                 dfs(grid,posx,posy,grid[posx][posy]+path);
//                 check[posx][posy] = false;
//             }
//         }

//     }
// };


//不同路径III
//https://leetcode.cn/problems/unique-paths-iii/description/
// class Solution {
//     int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};
//     int m = 0, n = 0;
//     int ret = 0;
//     int zeron = 0;
// public:
//     int uniquePathsIII(vector<vector<int>>& grid) {
//         m = grid.size(),n = grid[0].size();
//         int x = 0,y = 0;
//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//             {
//                 if(grid[i][k] == 1) x = i,y = k;
//                 if(grid[i][k] == 0) ++zeron;
//             }
//         zeron += 1; //当走到2时也会+1步数 将2也算入步数
//         grid[x][y] = -1;
//         dfs(grid,x,y,0);
//         return ret;
//     }

//     void dfs(vector<vector<int>>& grid,int x,int y,int step)
//     {
//         if(grid[x][y] == 2)
//         {
//             if(step == zeron) ++ret;
//             return;
//         }

//         for(int i = 0;i<4;++i)
//         {
//             int px = x+dx[i],py = y+dy[i];
//             if(px >= 0 && px < m && py < n && py >= 0 && grid[px][py] != -1)
//             {
//                 int tmp = grid[x][y];
//                 grid[x][y] = -1;
//                 dfs(grid, px, py,step+1);
//                 grid[x][y] = tmp;
//             }
//         }
//     }
// };

